package leetcode.code2002;

import java.util.HashMap;

import leetcode.helper.MaxDebug;

/**
 *
 * 执行用时：96 ms, 在所有 Java 提交中击败了65.59%的用户
 *
 * 内存消耗：39.1 MB, 在所有 Java 提交中击败了6.99%的用户
 *
 * 通过测试用例：226 / 226
 *
 * @author CaoYu
 * @date 2021年12月5日
 * @description
 */
public class Solution1 extends S2002 {

	@Override
	public int maxProduct(String s) {
		int len = s.length();
		int range = (1 << len) - 1;
		HashMap<Integer, Integer> dp = new HashMap<>();
		return this.f(s.toCharArray(), 0, 0, range, dp);
	}

	private int f(char[] charArray, int index, int s1, int range, HashMap<Integer, Integer> dp) {
		if (index == charArray.length) {
			if (dp.containsKey(s1)) {
				return dp.get(s1);
			}
			String str1 = this.string(charArray, s1);
			String str2 = this.string(charArray, s1 ^ range);
			int len1 = this.longestPalindromeSubseq(str1);
			int len2 = this.longestPalindromeSubseq(str2);
			int ans = len1 * len2;
			dp.put(s1, ans);
			dp.put(s1 ^ range, ans);
			return ans;
		}
		int ans1 = this.f(charArray, index + 1, s1, range, dp);
		int ans2 = this.f(charArray, index + 1, s1 | (1 << index), range, dp);
		return Math.max(ans1, ans2);
	}

	private String string(char[] charArray, int s1) {
		StringBuffer sb = new StringBuffer();
		int p = charArray.length - 1;
		while (s1 > 0) {
			if ((s1 & 1) == 1) {
				sb.insert(0, charArray[p]);
			}
			p--;
			s1 >>= 1;
		}
		return sb.toString();
	}

	public int longestPalindromeSubseq(String s) {
		int n = s.length();
		if (n == 0)
			return 0;
		int[][] dp = new int[n][n];
		for (int i = n - 1; i >= 0; i--) {
			dp[i][i] = 1;
			char c1 = s.charAt(i);
			for (int j = i + 1; j < n; j++) {
				char c2 = s.charAt(j);
				if (c1 == c2) {
					dp[i][j] = dp[i + 1][j - 1] + 2;
				} else {
					dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
				}
			}
		}
		return dp[0][n - 1];
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug4();
		MaxDebug.debug14(so);

	}

}
